package Atop100.heap;

import java.util.PriorityQueue;

public class Class295 {
    class   MedianFinder{
        PriorityQueue <Integer>  A;
        PriorityQueue <Integer>  B;
        public MedianFinder() {
            //TODO:2024/1/4  小顶堆   存较大的一半元素
            A= new PriorityQueue<>();
            //TODO:2024/1/4 大顶堆  存较小的一半元素
            B= new PriorityQueue<>((a,b)->(b-a));
        }
        public void addNum(int num) {
            if (A.size()!=B.size()){
                B.add(num);
                A.add(B.poll());
            }else {
                A.add(num);
                B.add(A.poll());
            }
        }
        public double findMedian() {
              return  A.size()==B.size()?(A.peek()+B.peek())/2.0:B.peek();
        }
    }

    public static void main(String[] args) {
        Class295 class295 = new Class295();
        MedianFinder medianFinder = class295.new MedianFinder();
        for (int i = 0; i < 10; i++) {
            medianFinder.addNum(i);
        }
        System.out.println(medianFinder.findMedian());

    }



}
